package recursion;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/*

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。
每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。
假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，
问过Z个月以后，共有成虫多少对？0 <= x <= 20, 1 <= y <= 20, x <= z <= 50。
输入
x,y,z的数值。
输出
过Z个月以后，共有成虫对数。
样例输入
1 2 8
样例输出
37


第n个月的成虫对数 = 第n-2个月的成虫对数 + 第n-2个月的卵对数
第n-2个月的卵对数 = 第n-2个月刚产的卵 + 第n-2个月1个月大的卵
                = 在第n-2个月过了x个月的成虫对数*y + 在第n-3个月过了x个月的成虫对数*y
                = 第n-2-x个月的成虫对数*y + 第n-3-x个月的成虫对数*y



 */
public class InsectsPropagation {
    static InOut0 io = new InOut0();
    int x, y, z;
    int result;
    int result2;
    int[] arr;
    public InsectsPropagation() {
        x = io.nextInt();
        y = io.nextInt();
        z = io.nextInt();
        result = f(z);
        result2 = way2(z);
        arr = new int[z + 1];
        takeArr();
    }
    // 递归
    public int f(int z) {
        if (z-3-x >= 0) {
            return f(z-2) + f(z-2-x) * y + f(z-3-x) * y;
        } else if (z >= 0 && z < x + 2) {
            return 1;
        } else if (z == x + 2) {
            return 1 + y;
        }
        return 0;
    }
    // dp
    public void takeArr() {
        for (int i = 0; i <= z; i++) {
            if (i-3-x >= 0) {
                arr[i] = arr[i-2] + arr[i-2-x] * y + arr[i-3-x] * y;
            } else if (i >= 0 && i < x + 2) {
                arr[i] = 1;
            } else if (i == x + 2) {
                arr[i] = 1 + y;
            } 
        }
    }
    // 解法2
    public int way2(int z) {
        int[] adults = new int[z+2];
        int[] babys = new int[z+2];
        for (int i = 0; i <= x; i++) {
            adults[i] = 1;
            babys[i] = 0;
        }
        for (int i = x+1; i <= z+1; i++) {
            babys[i] = adults[i-x] * y;
            adults[i] = adults[i-1] + babys[i-2];
        }
        return adults[z+1];
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        /*
        while (io.hasNext()) {
            InsectsPropagation inp = new InsectsPropagation();
            io.out.println(inp.result);
            io.out.flush();
        }
        */
        InsectsPropagation inp = new InsectsPropagation();
        io.out.println(Arrays.toString(inp.arr));
        io.out.println(inp.result);
        io.out.println(inp.result2);
        io.out.flush();
    }

}
class InOut0 {
    BufferedReader br;
    StringTokenizer tok;
    PrintWriter out;
    
    InOut0() {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
    }
    
    public boolean hasNext() {
        while (tok == null || !tok.hasMoreElements()) {
            try {
                tok = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                // TODO Auto-generated catch block
                return false;
            }
        }
        return true;
    }
    
    public String next() {
        if (hasNext()) {
            return tok.nextToken();
        }
        return null;
    }
    
    public int nextInt() {
        return Integer.parseInt(next());
    }
}
